Count and say

Time: O(Nx2^N); Space: O(2^N); easy

The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221

  • 1 is read off as “one 1” or 11.

  • 11 is read off as “two 1s” or 21.

  • 21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note:

  • Each term of the sequence of integers will be represented as a string.

Example 1:

Input: n = 1

Output: “1”

Explanation:

  • This is the base case.

Example 2:

Input: n = 4

Output: “1211”

Explanation:

  • For n = 3 the term was “21” in which we have two groups “2” and “1”,

  • “2” can be read as “12” which means frequency = 1 and value = 2,

  • the same way “1” is read as “11”,

  • so the answer is the concatenation of “12” and “11” which is “1211”.

Hints:

  1. The following are the terms from n=1 to n=10 of the count-and-say sequence:

  2. 1

  3. 11

  4. 21

  5. 1211

  6. 111221

  7. 312211

  8. 13112221

  9. 1113213211

  10. 31131211131221

  11. 13211311123113112211

  • To generate the nth term, just count and say the n-1th term.

[1]:

class Solution1(object):

    def getNext(self, seq):
        i, next_seq = 0, ""

        while i < len(seq):
            cnt = 1
            while i < len(seq) - 1 and seq[i] == seq[i + 1]:
                cnt += 1
                i += 1
            next_seq += str(cnt) + seq[i]
            i += 1
        return next_seq

    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        seq = "1"
        for i in range(n - 1):
            seq = self.getNext(seq)
        return seq

[2]:

s = Solution1()
n = 1
assert s.countAndSay(n) == "1"
n = 4
assert s.countAndSay(n) == "1211"